1. Field of the Invention
The present invention relates to a discrete multitone transmission technology and, more particularly, to a Fast Fourier Transform device for a discrete multitone system, wherein the Fast Fourier Transform device is realized with a parallel lattice architecture by simplifying the demand for multipliers and adders through conjugate symmetry to further reduce manufacturing cost.
2. Description of the Prior Art
The recent progress of Internet access has led to the urgent demand for high-speed data transmission technology. Various multiple modulation/demodulation circuits, such as carrierless-amplitude-phase (CAP), discrete multitone modulation (DMT), quadrature amplitude modulation (QAM) technologies, have been proposed to break through the transmission bottleneck of twisted-pair phone lines. Among these advanced modulation schemes, the DMT can achieve highest transmission rate since it incorporates lots of advanced DSP techniques, such as dynamic bit allocation, multi-dimensional tone encoding, frequency-domain equalization, etc. As a consequence, the ADSL (asymmetric digital subscriber lines) standard committee has chosen the DMT as the physical-layer transmission standard.
In a conventional DMT system, Fast Fourier Transform (FFT) algorithm is basically adopted. However, Fast Fourier Transform is a reversible operation, which includes Forward Fast Fourier Transform, hereinafter F-FFT, and Inverse Fast Fourier Transform, hereinafter I-FFT. Therefore, the term "Fast Fourier Transform" as used in the following description includes both F-FFT and I-FFT, unless otherwise specified.
The Fast Fourier Transform device as embodied in a discrete multitone system of prior art is commonly realized with a butterfly structure formed with Fast Fourier Transform algorithm of decimation-in-time and decimation-in-frequency. Such a butterfly structure will require (6Nlog.sub.2 2N) real adders and (4Nlog.sub.2 2N) real multipliers for 2N-point Fast Fourier Transform device. Taking 512 (N=256) points for example, 13824 adders and 9216 multipliers will be needed. Hence, such a large demand for hardware components will increase the complexity of wiring and the required layout area, and it will become difficult for very large scale integrated (VLSI) circuit implementation due to increasing manufacturing cost.